package com.example.algorithm.no0001.solution;

import com.example.algorithm.no0001.Solution;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 两数之和-两遍hashMap
 * 时间复杂度：O(n)，
 * 我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。
 * 空间复杂度：O(n)，
 * 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。
 * @ClassName SumTwoNum
 * @Author Administrator
 * @Date 2020/5/16 12:48
 * @Version 1.0.0
 */
public class HashMapSolution2 implements Solution {

    /**
     *  {2, 7, 11, 15}  9
     * @param nums      {2, 7, 11, 15}
     * @param target    9
     * @return
     */
    @Override
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        return null;
    }
}
